How to Cooperate Locally to Improve Global Privacy in Social Networks? On Amplification of Privacy Preserving Data Aggregation

摘要

In many systems privacy of users depends on the number of participantsapplying collectively some method to protect their security. Indeed, there arenumerous already classic results about revealing aggregated data from a set ofusers. The conclusion is usually as follows: if you have enough friends to"aggregate" the private data, you can safely reveal your private information. Apart from data aggregation, it has been noticed that in a wider contextprivacy can be often reduced to being hidden in a crowd. Generally, theproblems is how to create such crowd. This task may be not easy in somedistributed systems, wherein gathering enough "individuals" is hard forpractical reasons. Such example are social networks (or similar systems), where users have onlya limited number of semi trusted contacts and their aim is to reveal someaggregated data in a privacy preserving manner. This may be particularlyproblematic in the presence of a strong adversary that can additionally corruptsome users. We show two methods that allow to significantly amplify privacy with onlylimited number of local operations and very moderate communication overhead.Except theoretical analysis we show experimental results on topologies ofreal-life social networks to demonstrate that our methods can significantlyamplify privacy of chosen aggregation protocols even facing a massive attack ofa powerful adversary. We believe however that our results can have much wider applications forimproving security of systems based on locally trusted relations.